1. Field of the Invention
The present invention relates to techniques for efficiently determining the rank of items in a least-recently-used (LRU) list. More specifically, the invention relates to techniques for managing an LRU list so that the rank of data records in the list can be found efficiently, thereby reducing the frequency with which the list must be traversed and re-initialized.
2. Related Art
Caching techniques strive to provide rapid data access by loading frequently-used data from slower, large-capacity storage into faster cache memory. Since cache memories are typically much faster and smaller than the large-capacity storage, program performance depends heavily on the organization and functional behavior of the cache.
The choices of cache size and replacement strategy are key to cache performance. Temporal and spatial locality of data access have led to the common use of an LRU (least-recently-used) replacement strategy, where the item which was used least-recently is displaced when a new item is added to the cache.
However, determination of the ideal cache size remains a challenge. Currently, the best strategy for determining cache size involves simulating cache performance across a set of workloads. Since the volatility of the cache as a function of its size is an important consideration, such simulations must typically be run multiple times with varying cache sizes in order to generate statistically-meaningful hit rates. These simulation runs can be time-consuming, since the caches may be large and the system must track the previous access for every item in the cache. Furthermore, if the simulation tracks accesses using an LRU list, the process of managing such an LRU list requires constant maintenance of an ordered list of items, and a significant portion of the entire list may require re-enumeration upon every data access. As a result, list management and lookup operations consume a substantial portion of the simulation time.
Hence, what is needed is a method and an apparatus for managing an LRU list, such that the rank, or position, of data records can be determined efficiently.